# Given an array of integer ,try to sum up the maximum of the contiguous subarray 
# @Author: timlentse(tinglenxan@gmail.com)
# @Date: 2014-11-18
def findMaxSumOfSubArr(Arr):
    if not Arr:
        return 0
    else:
        currentSum = 0
        MaxSumOfSubArr = Arr[0]
        for x in Arr:
            if currentSum < 0:
                currentSum = x
            else:
                currentSum +=x
            MaxSumOfSubArr = currentSum if MaxSumOfSubArr<currentSum else MaxSumOfSubArr
    return MaxSumOfSubArr
testArr = [-1,-2,-3,6,-3,4,-7,-8,9]
print findMaxSumOfSubArr(testArr)
            